#ifndef	_PACKER_H_
#define	_PACKER_H_

#include <vector>
#include <algorithm>
#include <string>
#include <iterator>
#include <cmath>
#include <queue>
#include <functional>
#include <unordered_map>
#include <cstdlib>

#include <boost/random/uniform_real_distribution.hpp>
#include <boost/random/random_number_generator.hpp>
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/variate_generator.hpp>
#include <boost/math/constants/constants.hpp>
#include <boost/shared_ptr.hpp>
// polygon simplification
#include <boost/geometry/geometry.hpp>
#include <boost/geometry/geometries/linestring.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/algorithms/simplify.hpp>
#include <boost/thread.hpp>

#include <CGAL/Timer.h>
#include <CGAL/create_offset_polygons_2.h>

#include <Geex/basics/types.h>
#include <Geex/basics/file_system.h>
#include <glut_viewer/glut_viewer.h>

#include "../common/particle_circle.h"
#include "../common/containers.h"
#include "../common/potential_energy.h"
#include "../common/circle_union.h"
#include "../common/bin_packing.h"
#include "../common/polytope.h"
#include "discrete_field_system.h"
#include "field_energy.h"
#include "distance_field_grid_2.h"
#include "centralized_polygon_system.h"
#include "centralized_polygon_system_no_rot.h"
#include "polygon_triangulation.h"
#include "polygon_matcher.h"
#include "polygon_containment.h"
#include "../common/OptimalAssignment/iAuction.h"

namespace Field_packing 
{

	using namespace Geex;
	using namespace Packing_common;

	class Packing_graphics;

	class Packer 
	{
		//typedef boost::shared_ptr<Geex::Polygon_2> PolygonPrt;
		friend class Packing_graphics;

		typedef Polygon_triangulation::Triangulation_2 Triangulation_2;
		typedef Triangulation_2::Vertex_handle Vertex_handle;
		typedef Triangulation_2::Face_handle Face_handle;
		typedef Triangulation_2::Edge Edge;
		typedef Triangulation_2::Segment	Segment_2;
		typedef Triangulation_2::Point		Point_2;
		typedef Packing_polygon::Transformation_2 Transformation_2;
		typedef Packing_polygon::Vector	Vector_2;

		//typedef std::list< std::pair<Point_2, Point_2> > Hole_boundary;
	
	private:
		struct Push_top_sample_pnts : public std::unary_function<Vertex_handle, void>
		{
			Push_top_sample_pnts(double container_top) : cont_top(container_top) { }
			void operator()(Vertex_handle v) const
			{
				//std::cout<<"Pushing down...\n";
				if (v->point().y() > cont_top)
				{
					
					v->set_point(Point_2(v->point().x(), cont_top));
				}
			}
			double cont_top;
		};
		struct Transform_vertex : public std::unary_function<Vertex_handle, void>
		{
			Transform_vertex(const Transformation_2& t) : tran(t) { }
			void operator()(Vertex_handle vh) const 
			{
				Point_2 p = tran(vh->point());
				vh->set_point(p); 
			}
			Transformation_2 tran;
		};

	public:
		struct Hole
		{
			std::list<Segment_2> segments;
			double area;
			void clear() { segments.clear(); }
		};
	public:
		
		Packer(const std::string& polygon_fn, const std::string& debug_fn, double coverage_rate) ;
		~Packer();
		/* set methods */
		bool& toggle_rot() { return rot_allowed; }
		int& max_trials() { return nb_trials; }
		bool& toggle_upward_gravity() { return upward_gravity; }

		/* query methods */
		static Packer* instance() { return instance_ ; }
		inline size_t nb_polygons() const { return polygon_set.size(); }

		/* computation */
		void pack(unsigned int nb_trials);
		double cen_pack();
		// void fluctuate(); // deleted. check out svn for recover
		double& rm_scale_val() { return rm_scale; }
		void lower_container();
		void permute();
		void multistart_search(void (*update_draw)() = NULL);
		/* simulated anealing */
		void move_to_neighbor_state();
		void run_sa(void (*update_draw)() = NULL);

		/* geometry */
		void detect_bnd_holes(); // detect holes formed by tiles and container
		double* set_front_edge_sz() { return &front_edge_sz; }
		double* set_hole_face_sz() { return &hole_face_sz; }
		void fill_holes(); // fill the holes with current tiles
		void extract_vacant_neighbor();
		//void extract_CAT();
		void gen_delaunay();
		void update_triangulation() { pt.update_triangulation(); }

		/* miscellaneous */
		void get_bbox(double& x_min, double& y_min, double& z_min, double& x_max, double& y_max, double& z_max);
		/*
		** ONLY FOR DEBUG
		*/
		void plot();
		// draw the vacant sapce of the tiles in a nonneighboring group
		void draw_vacant_space(size_t group_id);
		double current_energy();

	private:
		
		void extract_vacant_neighbor(size_t idx, Hole& vnbnd);
		size_t permute(const std::list<int>& one_group);// permutation among one group
		// check containment between a hole and a tile
		bool overlap(const std::list<Segment_2>& hole, const Packing_polygon& pgn);

		void move(double dx, double dy);
		void hand_select(double mouse_x, double mouse_y);
		
		CGAL_polygon simplify_polygon(const CGAL_polygon& pgn);

		bool has_inclusion(const CGAL_polygon& out_pgn, const CGAL_polygon& in_pgn);
		// debug
		void write_polygon(const char* fn, const CGAL_polygon& pgn) const;
		
	private:
		static Packer* instance_ ;

		// geometry
		Rectangular_box *rbox;
		std::vector<Packing_polygon*> polygon_set;
		double total_volume;
		double rm_scale;
		Polygon_triangulation pt;
		//boost::shared_ptr<Delaunay_triangulation_2> pdt; // the Delaunay triagulation with edge sample points as the vertices

		std::vector< Hole > holes;
		//std::vector< std::list<Point_2> > cat_cells;
		// threshold value for hole detection, in percentage
		double front_edge_sz;
		double hole_face_sz;

		// swap
		std::vector< std::list<int> > groups;
		std::vector< Hole > vacant_space;
		// optimization
		bool rot_allowed;
		bool upward_gravity;

		// multistart
		int nb_trials;
		
		// debug
		size_t select_no;
		Sync_queue< std::vector<Parameter> > trans_queue;
		bool sync_draw;
		// discretization
		//Distance_field_grid_2* dfg;
		//Centralized_polygon_system *db_cps;

	} ;

}

#endif